package leetcode_core.leetcode_2;

public class CuttingRope {
    public int cuttingRope(int n) {
        //首先,我们知道如果只是拆分两个数的话,比如说我想拆分n,那么拆分后的结果就是x和n-x,x固定
        //n-x可以继续拆分,但是也可以选择不拆分,假设n-x继续拆分,拆分出(y,n-x-y)
        //然后我们发现这样的问题规模缩小了,但是解决办法与之前是一模一样的
        //状态:当前所拆分得到的数字状态
        //选择:是否将当前的数拆分成更多数之和,还是说直接乘上它就好了,直接取max进行选择取优
        //1.定义dp数组:表示当前这个dp[i],i所能拆分得到的各数之乘积的最大值
        //那么最终的返回值就是dp[n]
        int[] dp = new int[n+1];
        //2.确定base-case,0和1不能再被拆分
        dp[0] = dp[1] =1;
        //3.确定状态转移方程
        for(int i = 2;i<=n;i++){
            int max = 0;
            for(int j = 1;j<i;j++){
                max = Math.max(max,Math.max(j*(i-j),j*dp[i-j]));
            }
            dp[i] = max;
        }
        return dp[n];
    }
}
